package leetCode.solution;

import java.util.Random;

import com.alibaba.fastjson.JSON;

/**
 * 给你一个整数数组 nums，请你将该数组升序排列。
 * 
 * @author jerry
 * @ClassName: Solution912
 * @Description:TODO(描述这个类的作用)
 * @date 2022年12月15日 下午3:04:39
 */
public class Solution912 {
	public static void main(String[] args) {
		System.out.println(JSON.toJSONString(new Solution912()
				.heapSort(new int[] { 0,1,2,3,4,5,6 })));
//				.sortArray(new int[] { 2, 1, 5, 4, 3, 3, 6, 7, 8, 3, 1, 4, 6, 8, 5, 2, 4, 6, 9, 6, 3, 12, 1 })));
	}
	
	// 堆排
	public int[] heapSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return arr;
		}
		// O(N*logN)
//		for (int i = 0; i < arr.length; i++) { // O(N)
//			heapInsert(arr, i); // O(logN)
//		}
		// O(N)
		for (int i = arr.length - 1; i >= 0; i--) {
			heapify(arr, i, arr.length);
		}
		int heapSize = arr.length;
		swap(arr, 0, --heapSize);
		// O(N*logN)
		while (heapSize > 0) { // O(N)
			heapify(arr, 0, heapSize); // O(logN)
			swap(arr, 0, --heapSize); // O(1)
		}
		return arr;
	}
	
	public void heapify(int[] arr, int index, int heapSize) {
		int left = index * 2 + 1; // 左孩子的下标
		while (left < heapSize) { // 下方还有孩子的时候
			// 两个孩子中，谁的值大，把下标给largest
			int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
			// 父和较大的孩子之间，谁的值大，把下标给largest
			if(arr[largest] < arr[index]) break;
			swap(arr, largest, index);
			index = largest;
			left = index * 2 + 1;
		}
	}
	
	public void heapInsert(int[] arr, int index) {
		while (arr[index] > arr[(index - 1) / 2]) {
			swap(arr, index, (index - 1) / 2);
			index = (index - 1) / 2;
		}
	}
	
	
	// 快排
	
	public int[] quickSort(int[] nums) {
		randomizedQuicksort(nums, 0, nums.length - 1);
		return nums;
	}
	
	private void randomizedQuicksort(int[] nums, int l, int r) {
		if (l < r) {
			int range[] = partition(nums, l, r);
			randomizedQuicksort(nums, l, range[0] - 1);
			randomizedQuicksort(nums, range[1] + 1, r);
		}
	}

	private int[] partition(int[] nums, int l, int r) {
		int mid = nums[l + new Random().nextInt(r - l + 1)];
		int i = l;
		int size = 0;
		while (l <= r) {
			if (nums[l] > mid) {
				swap(nums, l, r--);
			} else if (nums[l] < mid) {
				swap(nums, l++, i++);
			} else {
				size++;
				l++;
			}
		}
		return new int[] { i, i + size - 1 };
	}

	private void swap(int[] nums, int l, int r) {
		int tmp = nums[l];
		nums[l] = nums[r];
		nums[r] = tmp;
	}
}
